package 力扣_数学思维题;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**1524. 和为奇数的子数组数目
 * @author zx
 * @create 2022-04-28 16:59
 */
public class 和为奇数的子数组数目 {
    /**
     解题思路
     分析题意需要求和为计数的子数组数目,根据数据量来说暴力肯定超时,则可以使用HashMap来记录当前前缀和中偶数和奇数的个数。
     1.当暴力的时候思考：
     得到前缀和数组之后,可以看当前位置i和其他位置上j的值分别是奇数还是偶数,当前仅当一奇一偶的时候中间部分之和为奇数。
     2.使用HashMap的时候思考：
     那既然只要知道前缀和数组中当前位置i和其他位置j上奇偶情况,先对前缀和数组处理每个数都%2获得奇偶情况再说.

     若当前数组位置上的值为0(偶)则希望前面有1(奇)出现,若有则说明会有和为奇数的子数组出现,1出现的个数就是可以组成的子数组的个数。
     若当前数组位置上的值为1(奇)则希望前面有0(偶)出现,若有则说明会有和为奇数的子数组出现,0出现的个数就是可以组成的子数组的个数。
     --后面再想了下其实只有0、1两个值，那直接开个数组记录就行或者直接两个变量代表0和1的数量就行，其他一样但数组或变量更快一点。
     同时需要更新当前位置上出现的值在map中的情况。

     map中首先需要put(0, 1)的原因：
     当仅有一个奇数构成符合条件的子数组的时候不能漏算。
     */
    public int numOfSubarrays(int[] arr) {
        int n = arr.length;
        int[] preSum = new int[n];
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        // 计算前缀和
        preSum[0] = arr[0];
        for(int i = 1; i < n; i++){
            preSum[i] = preSum[i - 1] + arr[i];
        }
        // 处理前缀和
        for(int i = 0; i < n; i++){
            preSum[i] %= 2;
        }
        int res = 0;
        int mod = 1000000007;
        for(int i = 0; i < n; i++){
            int cur = (preSum[i] == 0 ? 1 : 0);
            // 情况判断
            if(map.containsKey(cur)){
                res += map.get(cur);
                res %= mod;
            }
            // 更新map
            if(map.containsKey(preSum[i])){
                map.put(preSum[i],map.get(preSum[i]) + 1);
            }else{
                map.put(preSum[i],1);
            }
        }
        return res;
    }
    /**
     * @return 暴力解法(过不了)
     */
    public int numOfSubarrays2(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for(int i = 0;i < arr.length;i++){
            int sum = 0;
            for(int j = i;j < arr.length;j++){
                sum += arr[j];
                list.add(sum);
            }
        }
        int count = 0;
        for(Integer i : list){
            if(i % 2 == 1){
                count++;
            }
        }
        return count % (int)(Math.pow(10,9) + 7);
    }
}
